package heap.medium;

import java.util.HashMap;
import java.util.PriorityQueue;


/**
 * 前 K 个高频元素示例 1:
 *
 * 输入: nums = [1,1,1,2,2,3], k = 2
 * 输出: [1,2]
 * 示例 2:
 * 输入: nums = [1], k = 1
 * 输出: [1]
 * 链接：https://leetcode-cn.com/problems/top-k-frequent-elements
 */
public class TopKFrequentElements_347 {
    public int[] topKFrequent(int[] nums, int k) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }

        PriorityQueue<Integer> heap = new PriorityQueue<>((a, b) -> map.get(a) - map.get(b));
        for (Integer integer : map.keySet()) {
            heap.offer(integer);
            if (heap.size() > k)
                heap.poll();
        }

        int[] arr = new int[heap.size()];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = heap.poll();
        }
        return arr;
    }
}
